package com.yubest;

import java.util.ArrayList;
import java.util.List;

/**
 * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 *
 * [图片] img/0872_1.jpg
 *
 * 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
 *
 * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 *
 * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 *
 *  
 *
 * 示例 1：[图片] img/0872_2.jpg
 *
 *
 *
 * 输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
 * 输出：true
 * 示例 2：
 *
 * 输入：root1 = [1], root2 = [1]
 * 输出：true
 * 示例 3：
 *
 * 输入：root1 = [1], root2 = [2]
 * 输出：false
 * 示例 4：
 *
 * 输入：root1 = [1,2], root2 = [2,2]
 * 输出：true
 * 示例 5：[图片] img/0872_3.jpg
 *
 *
 *
 * 输入：root1 = [1,2,3], root2 = [1,3,2]
 * 输出：false
 *  
 *
 * 提示：
 *
 * 给定的两棵树可能会有 1 到 200 个结点。
 * 给定的两棵树上的值介于 0 到 200 之间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/leaf-similar-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/11 17:54
 */
public class P0872 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution872 {

    private List<Integer> leafs = new ArrayList<>();

    private int index = 0;

    /**
     * 思路：先获取root1的叶值序列，然后遍历root2的叶值序列，和root1的叶值序列相比较
     * @param root1
     * @param root2
     * @return
     */
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        getLeafs(root1);
        return leafSimilar(root2) && leafs.size() == index;
    }

    private void getLeafs(TreeNode node) {
        if (null == node) {
            return;
        }
        if (null == node.left && null == node.right) {
            leafs.add(node.val);
        }
        getLeafs(node.left);
        getLeafs(node.right);
    }

    private boolean leafSimilar(TreeNode node) {
        if (null == node || index >= leafs.size()) {
            return false;
        }
        if (null == node.left && null == node.right) {
            return node.val == leafs.get(index++);
        }
        return null != node.left && null != node.right
                ? leafSimilar(node.left) && leafSimilar(node.right)
                : leafSimilar(null != node.left ? node.left : node.right);
    }
}
